NAND flash memory, as well as other types of non-volatile memories (“NVMs”), are commonly used for mass storage. For example, consumer electronics such as portable media players or cellular telephones often include raw flash memory or a flash card to store music, videos, and other media.
Some non-volatile memories, such as NAND flash memory, may have memory locations that include initial defects or can develop defects through use. Also, memory locations may suffer from other error-causing phenomena, such as read disturb or charge retention issues. Thus, to ensure that data stored in these memory locations can be accurately retrieved, redundant information be computed and stored along with the data. For example, an error correcting code may be applied to the data prior its storage in the non-volatile memory.
An error correcting code may be measured by its “strength.” The strength, t, may indicate the number of errors (e.g., bit flips) that may be tolerated. Any additional errors may result in mis-corrections. A higher-strength error correcting code typically requires more redundant information for the same amount of data than a lower-strength error correcting code. Therefore, there is a tradeoff between the number of errors that can be corrected and the amount of space sacrificed in the non-volatile memory for storing redundant information.